import java.util.HashMap;
import java.util.Map;

/*
题目描述：最长不含重复字符的最长字符
方法：
动态规划

 */
public class E48 {
    public static void main(String[] args) {

        String str = "arabcacfr";
        int res1 = longestSubstringWithoutDuplication1(str);
        int res2 = longestSubstringWithoutDuplication1(str);
        System.out.println(res1);
        System.out.println(res2);
    }

    public static int longestSubstringWithoutDuplication1(String str){
        int curLength = 0;
        int maxLength = 0;
        int[] position = new int[26];
        for(int i = 0; i < 26; i++){
            position[i] = -1;
        }

        for(int i = 0; i < str.length(); i++){
            int preIndex = position[str.charAt(i) - 'a'];
            if(preIndex < 0 || i - preIndex > curLength){
                curLength++;
            }
            else{
                if(curLength > maxLength){
                    maxLength = curLength;
                }
                curLength = i - preIndex;
            }
            position[str.charAt(i) - 'a'] = i;
        }
        if(curLength > maxLength){
            maxLength = curLength;
        }
        return maxLength;
    }

    public static int longestSubstringWithoutDuplication2(String str){
        Map<Character, Integer> position = new HashMap<>();
        for(char c : str.toCharArray()){
            position.put(c, -1);
        }
        int curLength = 0;
        int maxLength = 0;
        for(int i = 0; i < str.length(); i++){
            int preIndex = position.get(str.charAt(i));//记录上次这个字符的位置
            if(preIndex < 0 || i - preIndex > curLength){//当前字符并没有出现过或者该字符距离上一次出现的距离已经大于当前最大距离
                curLength++;
            }
            else{//当前字符已经出现过并且距离上一次出现的距离小于当前距离
                if(curLength > maxLength){
                    maxLength = curLength;
                }
                curLength = i - preIndex;//更新当前距离
            }
            position.put(str.charAt(i),i);
        }
        if(curLength > maxLength){
            maxLength = curLength;
        }
        return maxLength;
    }
}
